#include "param.h"
#include "types.h"
#include "memlayout.h"
#include "elf.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"

#include "spinlock.h"
#include "proc.h"

/*

最核心的函数是：
  walk为虚拟地址找到PTE，
  mappages为新映射装载PTE。

  名称以kvm开头的函数操作内核页表；
  以uvm开头的函数操作用户页表；

  
*/


/*
 * the kernel's page table.
 全局内核页表
 */
pagetable_t kernel_pagetable;

// ld脚本里就存在的，指向内核代码的结尾
extern char etext[];  // kernel.ld sets this to end of kernel code.

// 蹦床页，见于trampoline.S
extern char trampoline[]; // trampoline.S

/*
 * create a direct-map page table for the kernel.
  * 这个函数用于为内核创建一个直接映射页表。
 */
void
kvminit()
{
  kernel_pagetable = (pagetable_t) kalloc();
  memset(kernel_pagetable, 0, PGSIZE);

  // uart registers
  // 串口寄存器
  kvmmap(UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  // virtio磁盘接口
  kvmmap(VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT
  kvmmap(CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  kvmmap(PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  // 将内核文本映射为可执行和只读。
  kvmmap(KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  // 将内核数据和我们将使用的物理RAM映射。
  kvmmap((uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);

  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  // 将用于陷阱进入/退出的跳板映射到内核中的最高虚拟地址。
  kvmmap(TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
}

////////////////////////////////////////////////////////////////

// 以下的函数都是为进程特有内核页表服务的，lab3的第二个实验需要用到

// 这是为进程特有的内核页表，设置映射的核心函数
void
proc_kvmmap(pagetable_t pgt, uint64 va, uint64 pa, uint64 sz, int perm)
{ 
  if(mappages(pgt, va, sz, pa, perm) != 0)
    panic("proc_kvmmap");
}



pagetable_t
proc_kernpgt()
{
  // 创建一个新的页表，作为进程独有的内核页表使用
  pagetable_t pgt = uvmcreate();

  //此映射同全局内核页表
  proc_kvmmap(pgt, UART0, UART0, PGSIZE, PTE_R | PTE_W);
  proc_kvmmap(pgt, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
  proc_kvmmap(pgt, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
  proc_kvmmap(pgt, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
  proc_kvmmap(pgt, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
  proc_kvmmap(pgt, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
  proc_kvmmap(pgt, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  return pgt;
}

////////////////////////////////////////////////////////////////////////////////////////////////

// Switch h/w page table register to the kernel's page table,
// and enable paging.
// 这个函数用于将页表切换到内核页表，并启用分页
void
kvminithart()
{
  // 将根页表页的物理地址写入寄存器satp，之后，CPU将使用内核页表转换地址
  w_satp(MAKE_SATP(kernel_pagetable));
  // 执行sfence.vma 刷新tlb
  sfence_vma();
}

// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va.  If alloc!=0,
// create any required page-table pages.
// 该函数用于返回页表中与虚拟地址va对应的页表项（PTE）的地址。
// 具体来说，这个函数接受一个页表pagetable和一个虚拟地址va作为输入，并返回与该虚拟地址对应的页表项的地址

// 预备知识：C语言中指针和数组对地址的操作技巧

// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
//   39..63 -- must be zero.
//   30..38 -- 9 bits of level-2 index.
//   21..29 -- 9 bits of level-1 index.
//   12..20 -- 9 bits of level-0 index.
//    0..11 -- 12 bits of byte offset within the page.
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");

  // 先从2级页表开始，然后逐级向下查找
  for(int level = 2; level > 0; level--) {

// #define PGSHIFT 12  // bits of offset within a page
//#define PXSHIFT(level)  (PGSHIFT+(9*(level)))

//#define PXMASK          0x1FF // 9 bits   0001 1111 1111

// 从va中提取出level级的索引，其实就是中间第N个9位
//#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)

    // 从虚拟地址va中提取出level级的索引，然后根据这个索引找到对应的PTE
    //相当于: idx = PX(level, va)  从虚拟地址中提取出第level级的索引
    // pte_t 和 pagetable_t都是 uint64，为的就是匹配64位地址

    // Q问题 :&pagetable为什么要用&取地址？和[]放在一起会是什么？

    pte_t *pte = &pagetable[PX(level, va)];

    // Q问题：这里为什么要用指针？

    // 如果这个PTE已经映射了一个物理页，就返回这个PTE
    if(*pte & PTE_V) {

      // pte[44,10]
      // pa [44,12]
      // 拿到pte之后，只要前44位就好了，后面填充2个多余的0位就行
      //#define PTE2PA(pte) (((pte) >> 10) << 12)

      //
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {

      // 如果这个PTE没有映射物理页，就分配一个新的页表页
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      
      // 将pagetable物理地址转换为PTE，然后设置权限和有效位
      // 将这个页表页的PTE设置为有效
// #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }

  //
  return &pagetable[PX(0, va)];
}

// 将一个虚拟地址转换成一个物理地址
// 如果没有映射，返回0
// 只允许在用户页上使用
// Look up a virtual address, return the physical address,
// or 0 if not mapped.
// Can only be used to look up user pages.
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
//  给内核页表加一个映射，仅在启动时使用，不刷新TLB或启用分页。
// va: 虚拟地址
// pa: 物理地址
// sz: 映射大小
// perm: 权限
void
kvmmap(uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kernel_pagetable, va, sz, pa, perm) != 0)
    panic("kvmmap");
}


// 将一个内核虚拟地址转换成一个物理地址。只会在栈上的地址上使用。
// 假设va是页面对齐的。
// WARN:注意是在哪个页表上调用的，内核全局页表or用户自身页表

// translate a kernel virtual address to
// a physical address. only needed for
// addresses on the stack.
// assumes va is page aligned.
uint64
kvmpa(uint64 va)
{
  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;
  
  pte = walk(myproc()->kern_pagetable, va, 0);
  if(pte == 0)
    panic("kvmpa pte==0");
  if((*pte & PTE_V) == 0)
    panic("kvmpa PTE_V");
  pa = PTE2PA(*pte);
  return pa+off;
}

// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned. Returns 0 on success, -1 if walk() couldn't
// allocate a needed page-table page.
// 为从va开始的虚拟地址创建指向从pa开始的物理地址的PTE。 va和size可能不对齐。 
// 成功时返回0，如果walk（）无法分配所需的页表页，则返回-1。
int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  uint64 a, last;
  pte_t *pte;

  // 从va开始的虚拟地址向下舍入到页面边界
  a = PGROUNDDOWN(va);

  last = PGROUNDDOWN(va + size - 1);

  for(;;){
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    
    if(*pte & PTE_V)
      panic("remap");

    *pte = PA2PTE(pa) | perm | PTE_V;

    if(a == last)
      break;

    // 继续下一个页面
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

// 删除从 va 开始的 n 个映射页。映射必须存在。
// 可选择释放物理内存。
// Remove npages of mappings starting from va. va must be
// page-aligned. The mappings must exist.
// Optionally free the physical memory.
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}



// 创造一个空的用户页表
// 返回0表示内存不足
// create an empty user page table.
// returns 0 if out of memory.
pagetable_t
uvmcreate()
{
  pagetable_t pagetable;
  pagetable = (pagetable_t) kalloc();
  if(pagetable == 0)
    return 0;
  memset(pagetable, 0, PGSIZE);
  return pagetable;
}

// 将用户初始代码加载到第一个进程的分页表地址 0 中。
// sz必须小于一个页面
// Load the user initcode into address 0 of pagetable,
// for the very first process.
// sz must be less than a page.
void
uvminit(pagetable_t pagetable, uchar *src, uint sz)
{
  char *mem;

  if(sz >= PGSIZE)
    panic("inituvm: more than a page");
  mem = kalloc();
  memset(mem, 0, PGSIZE);
  mappages(pagetable, 0, PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_X|PTE_U);
  memmove(mem, src, sz);
}

// 分配PTE和物理内存，以便从oldsz增长到newsz，newsz不需要对齐到页面。如果出错，则返回新大小或0。
// Allocate PTEs and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}


// 重新分配用户页面以把进程大小从oldsz调整到newsz。
// oldsz和newsz不需要对齐到页面，newsz不需要小于oldsz。
// oldsz可以大于实际进程大小。返回新进程大小。
// Deallocate user pages to bring the process size from oldsz to
// newsz.  oldsz and newsz need not be page-aligned, nor does newsz
// need to be less than oldsz.  oldsz can be larger than the actual
// process size.  Returns the new process size.
uint64
uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  if(newsz >= oldsz)
    return oldsz;

  if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
  }

  return newsz;
}

// 递归的释放页表页。
// 所有叶子映射必须已经被删除。
// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void
freewalk(pagetable_t pagetable)
{
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte);
      freewalk((pagetable_t)child);
      pagetable[i] = 0;
    } else if(pte & PTE_V){
      panic("freewalk: leaf");
    }
  }
  kfree((void*)pagetable);
}

// 释放用户内存页，然后释放页表
// Free user memory pages,
// then free page-table pages.
void
uvmfree(pagetable_t pagetable, uint64 sz)
{
  if(sz > 0)
    uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
  freewalk(pagetable);
}

/*
给定父进程的页表，将其内存复制到子进程的页表中。
同时复制页表和物理内存。
成功返回 0，失败返回 -1.
失败时释放已分配的页面。
*/
// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if((mem = kalloc()) == 0)
      goto err;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}


// 将 PTE 标记为用户访问无效。
// 用于执行用户堆栈保护页面。--guard page
// mark a PTE invalid for user access.
// used by exec for the user stack guard page.
void
uvmclear(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  
  pte = walk(pagetable, va, 0);
  if(pte == 0)
    panic("uvmclear");
  *pte &= ~PTE_U;
}

/////////////////////////////////////////////////////////////////////
// cpy_in/out相关

// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

// 您的工作是将用户空间的映射添加到每个进程的内核页表（上一节中创建）
// 
// 1、用户空间和内核空间虚拟地址上是有交叉的地方吗，
//  不然用户空间的映射，如果其虚拟地址已经在内核页表里被占用了，那就会错误

// 2、如果用户空间的映射全部被添加到了内核页表，那么用户空间的页表还有什么用？
//    猜测，是因为内核空间的内核代码部分只能k权限访问，用户访问要直接报错的
//    ----去看看页表pte权限里，有没有规定u/k访问权限的地方啊

// 从用户态拷贝到内核态。
// 从pagetable指定页表的虚拟地址srcva处，拷贝len字节到dst处。
// 这个dst是内核态的地址。
// 返回0成功，-1失败。
// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){

    // va0是srcva向下取整的地址，需要页面对齐
    va0 = PGROUNDDOWN(srcva);
    
    // pa0是这个va0对应的物理地址
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;

    // n是这个va0对应的物理页的剩余空间
    // srcva不一定对齐page，所以前面用PGROUNDDOWN向下取整了
    // srcva-va就是它距离下面page的间隙距离
    // pasize-这个数字，就是srcva距离上面page的距离，也就是需要被复制的字节数
    n = PGSIZE - (srcva - va0);
    if(n > len)
      n = len;

    // dst应该也是proc的kern_pgt的才是，那么应该在这个页表里找到这个va对应的pa？

    // (pa0 + (srcva - va0))是什么意思
    // pa0是向下取整的page所对应的物理地址，
    // srcva-pa是间隙
    // 二者相加，就是srcva对应的实际物理地址
    memmove(dst, (void *)(pa0 + (srcva - va0)), n);

    // 问题来了，为什么第二个参数，src要用物理地址？
    // 这里应该走的就是内核态了，那么应该就是内核页表咯，全局内核页表解析pa，应该也不对吧

    // 内核地址空间和用户地址空间是分开的，内核地址空间是直接映射的，所以直接用物理地址？

    // 内核地址在memlayout里到底怎么划分的？


    // 已经拷贝完n个字节，len-=n
    len -= n;
    // 目标地址往后移动n个字节
    dst += n;
    //虚拟源地址为什么是va0+PGSIZE？为什么是向后移动一个页面？
    // 回答：因为va0是srcva向下取整的最近page，复制是以page进行的
    srcva = va0 + PGSIZE;
  }
  return 0;
}

int
copyin_new(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{

/*
0、 将用户空间的映射添加到每个进程的内核页表
    找到用户空间的页表在哪里加的，每次加入的时候，额外加一份进内核页表？
    他们之间的虚拟地址不会重复吗？
    进程的地址空间安排是怎么样的？内核态的地址空间安排呢？他们各自的活动范围怎么订的？

    

*/

  return 0;
}


// 从用户态拷贝一个以null结尾的字符串到内核态。
// 从pagetable指定页表的虚拟地址srcva处，拷贝字节到dst处，直到遇到'\0'或者max。
// 成功返回0，失败返回-1。
// Copy a null-terminated string from user to kernel.
// Copy bytes to dst from virtual address srcva in a given page table,
// until a '\0', or max.
// Return 0 on success, -1 on error.
int
copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
{
  uint64 n, va0, pa0;
  int got_null = 0;

  while(got_null == 0 && max > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (srcva - va0);
    if(n > max)
      n = max;

    char *p = (char *) (pa0 + (srcva - va0));
    while(n > 0){
      if(*p == '\0'){
        *dst = '\0';
        got_null = 1;
        break;
      } else {
        *dst = *p;
      }
      --n;
      --max;
      p++;
      dst++;
    }

    srcva = va0 + PGSIZE;
  }
  if(got_null){
    return 0;
  } else {
    return -1;
  }
}


/////////////////////////////////////////////////////////////////////
// 打印页表相关


int level = 1;


void printfdot(int level)
{
  for(int i = 0; i < level; i++){
    printf("..");
  }
}

/*
1.最多遍历三层，每一层都是一个页表
2.如何知道有效和无效？--------pte最后的flag进行判断

*/

/*
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
*/

// 0x0000000021fda801---
// 0010 0001 1111 1101 1010 1000 0000 0001


void vmprint_helper(pagetable_t pagetable)
{
  uint64 child = 0;
  pte_t pte = 0;

  // 递归打印页表，一个页表一共有512项，先找到其中的有效项目
  for(int i = 0; i < 512; i++){
    // 获取第i个PTE项
   pte = pagetable[i];
    // 叶子节点，一定是R|W|X的
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X))){
      child = PTE2PA(pte);
      
      printfdot(level);
      printf("%d: pte %p pa %p\n",  i, pte, child);

    }else if(pte & PTE_V){
      // 分支节点的flag不是R|W|X的，这是规定？！
      child = PTE2PA(pte);
      printfdot(level);
      printf("%d: pte %p pa %p\n", i, pte, child);

      level++;
      if(level > 3){
        panic("level: bigger than 3");
      }
      
      // 如果还不是叶子节点，递归向下查找
      vmprint_helper((pagetable_t)child);
      
      level--;
    }
  }
}

// 0x0000000021fdac1f 
//0010 0001 1111 1101 1010 1100 0001 1111
void vmprint(pagetable_t pagetable)
{

  // 首先打印页表的地址
  printf("page table %p\n", pagetable);

  vmprint_helper(pagetable);
}
